package com.lw.leetcode.stack.b;

import com.lw.test.util.Utils;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 2434. 使用机器人打印字典序最小的字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/10 14:52
 */
public class RobotWithString {

    public static void main(String[] args) {
        RobotWithString test = new RobotWithString();

        // azz
//        String str = "zza";

        // abc
//        String str = "bac";

        // addb
//        String str = "bdda";

        //
        String str = Utils.getStr(100000, 'z', 'z');

        String s = test.robotWithString(str);
        System.out.println(s);
    }

    public String robotWithString(String s) {
        int[] arr = new int[26];
        int length = s.length();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            arr[aChar - 'a']++;
        }
        Stack<Character> items = new Stack<>();
        int min = getMin(arr);
        StringBuilder sb = new StringBuilder(length);
        for (int i = 0; i < length; i++) {
            while (!items.isEmpty() && items.peek() - 'a' <= min) {
                sb.append(items.pop());
            }
            char c = chars[i];
            int t = c - 'a';
            if (t == min) {
                sb.append(c);
                arr[t]--;
                min = getMin(arr);
            } else {
                items.add(c);
                arr[t]--;
            }
        }
        while (!items.isEmpty()) {
            sb.append(items.pop());
        }
        return sb.toString();
    }

    private int getMin(int[] arr) {
        for (int i = 0; i < 26; i++) {
            if (arr[i] > 0) {
                return i;
            }
        }
        return -1;
    }

}
